package com.xsherl.leetcode.solution;

public class PowxN {

    /**
     * 数理知识：
     *  1. (x ^ 2) ^ y = x ^ 2y
     *  2. x ^ m * x ^ n = x ^ (m + n)
     *  3. x ^ (-m) = 1 / (x ^ m)
     * 示例：
     *   x ^ 18 = (((x ^ 2) ^ 2) ^ 2) ^ 2 * x * x
     */
    public double myPow(double x, int n) {
        if (n == 0){
            return 1D;
        }
        if (x == 1){
            return 1D;
        }
        double res = x;
        long N = Math.abs((long) n);
        long squareCount = 2;
        while (squareCount <= N) {
            res *= res;
            squareCount *= 2;
        }
        long t = N - squareCount / 2;
        while (t > 0){
            res *= x;
            t--;
        }
        if (n < 0){
            return 1 / res;
        }
        return res;
    }

    public static void main(String[] args) {
        double x = 2.00000;
        int n = -2147483648;
        double v = new PowxN().myPow(x, n);
        System.out.println(v);
    }

}
